from functools import cache
from typing import *
from math import inf


class Solution:
    def maximalPathQuality(
        self, values: List[int], edges: List[List[int]], maxTime: int
    ) -> int:
        n = len(values)
        costs = [[inf] * n for _ in range(n)]
        nexts = [[] for _ in range(n)]
        for u, v, t in edges:
            costs[u][v] = t
            costs[v][u] = t
            nexts[u].append(v)
            nexts[v].append(u)

        @cache
        def f(id, time, pid):
            if time < 20:
                return 0
            ans = values[id]
            next = []
            for nxt in nexts[id]:
                if nxt != pid:
                    next.append(nxt)
            limit = 1 << len(next)
            for i in range(1, limit):
                cur, cost = 0, 0
                for j in range(len(nxt)):
                    if (i >> j) & 1 == 1:
                        cost += costs[id][next[j]]
                if cost <= time:
                    pass

            return ans

        return f(0, maxTime, -1)


s = Solution()
print(
    s.maximalPathQuality(
        values=[0, 32, 10, 43], edges=[[0, 1, 10], [1, 2, 15], [0, 3, 10]], maxTime=49
    )
)
